1244. Design A Leaderboard
Medium

Design a Leaderboard class, which has 3 functions:

  1. addScore(playerId, score): Update the leaderboard by adding score to the given player's score. If there is no player with such id in the leaderboard, add him to the leaderboard with the given score.
  2. top(K): Return the score sum of the top K players.
  3. reset(playerId): Reset the score of the player with the given id to 0 (in other words erase it from the leaderboard). It is guaranteed that the player was added to the leaderboard before calling this function.

Initially, the leaderboard is empty.

 

Example 1:

Input: 
["Leaderboard","addScore","addScore","addScore","addScore","addScore","top","reset","reset","addScore","top"]
[[],[1,73],[2,56],[3,39],[4,51],[5,4],[1],[1],[2],[2,51],[3]]
Output: 
[null,null,null,null,null,null,73,null,null,null,141]

Explanation: 
Leaderboard leaderboard = new Leaderboard ();
leaderboard.addScore(1,73);   // leaderboard = [[1,73]];
leaderboard.addScore(2,56);   // leaderboard = [[1,73],[2,56]];
leaderboard.addScore(3,39);   // leaderboard = [[1,73],[2,56],[3,39]];
leaderboard.addScore(4,51);   // leaderboard = [[1,73],[2,56],[3,39],[4,51]];
leaderboard.addScore(5,4);    // leaderboard = [[1,73],[2,56],[3,39],[4,51],[5,4]];
leaderboard.top(1);           // returns 73;
leaderboard.reset(1);         // leaderboard = [[2,56],[3,39],[4,51],[5,4]];
leaderboard.reset(2);         // leaderboard = [[3,39],[4,51],[5,4]];
leaderboard.addScore(2,51);   // leaderboard = [[2,51],[3,39],[4,51],[5,4]];
leaderboard.top(3);           // returns 141 = 51 + 51 + 39;

 

Constraints:

  • 1 <= playerId, K <= 10000
  • It's guaranteed that K is less than or equal to the current number of players.
  • 1 <= score <= 100
  • There will be at most 1000 function calls.
Accepted
22,737
Submissions
34,030
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
What data structure can we use to keep the players' data?
Show Hint 2
Keep a map (dictionary) of player scores.
Show Hint 3
For each top(K) function call, find the maximum K scores and add them.

Average Rating: 4.50 (12 votes)

Premium

Overview

There are a lot of implementations for this particular problem out there. The problem statement is pretty straightforward on the surface:

  1. We need to maintain a list of playerId to score mappings.
  2. Whenever required, obtain the top K scores, add them up, and return them.
  3. Finally, reset the score for a particular player.

We will start with the most basic, brute-force implementations for this problem and then move on to slightly complex implementations. To understand, what these complicated implementations will be using, we need to see the basic requirement of this problem.

We have a dynamically updating list of values and we need to be able to extract the top-k elements from that list.

Whenever we have such a problem statement which requires us to obtain the top-K values from a list which is dynamically updating, relying on a priority-queue seems like a good bet. A heap is one of the best data structures for handling such a requirement. So, we will be looking at a solution that makes use of the heap data structure.

Additionally, we will be looking at a binary search tree based solution. Although the heap is a great data structure for finding the top-K elements from a list without having to actually sort the list, it is not great at find-and-update kind of operations. General rule of thumb with the heap data structure is to use lazy-updates rather than having to traverse and update the entries themselves. We won't get a deterministic performance if we resort to lazy score updates here because we don't know the number of update operations and hence, the size of the heap can continue to grow if we have millions of score updates and no top-K function calls (or proportionally lower).




Approach 1: Brute Force

The brute-force approach is pretty straightforward in the sense that we will maintain a dictionary of playerId as the key and the score as the dictionary. Then, for each top operation, we will simply obtain all the values from the dictionary, sort them, and the obtain the top K elements.

Algorithm

  1. Initialize a dictionary scores that will use the playerId as the key and score as the value.
  2. addScore ~
    • Simply update the dictionary with the new score for the player.
    • If the player doesn't exist, initialize the score to score
  3. top ~
    • Obtain a list of all the values from the dictionary.
    • Sort the list in reverse order.
    • Sum up the first K values from the sorted list.
  4. reset ~
    • Delete the entry containing the playerId
    • Note that we can also set the value (score) to 0. The only disadvantage of this is that we will be sorting even reset players in the top function. This doesn't matter much for smaller test cases though.

Implementation

Complexity Analysis

  • Time Complexity:

    • O(1)O(1) for addScore.
    • O(1)O(1) for reset.
    • O(NlogN)O(N \text{log}N) for top where NN represents the total number of players since we sort all of the player scores and then take the top K from the sorted list.
  • Space Complexity:

    • O(N)O(N) used by the scores dictionary and also by the new list formed using the dictionary values in the top function.


Approach 2: Heap for top-K

This is a slight modification to the previous approach in that instead of sorting the list of the values, we will be making use of a min-heap to find the top-K values. This is a slightly modified version of the previous implementation.

Algorithm

  1. Initialize a dictionary scores that will use the playerId as the key and score as the value.
  2. addScore ~
    • Simply update the dictionary with the new score for the player.
    • If the player doesn't exist, initialize the score to score
  3. top ~
    • Initialize a new min-heap, scoreHeap.
    • Iterate over the first K values in the dictionary and add them to the heap.
    • Then, for the rest of the NKN-K values, we will simply do the following. We will add the new value to the heap, and pop the smallest value from the heap. In doing this, we maintain the size of the heap to K and also remove the smaller of the two values.
    • We do this for all of the NKN-K values and then, simply add up all the values remaining in the heap since those would be the largest K values left.
  4. reset ~
    • Delete the entry containing the playerId
    • Note that we can also set the value (score) to 0. The only disadvantage of this is that we will be sorting even reset players in the top function. This doesn't matter much for smaller test cases though.

Implementation

Complexity Analysis

  • Time Complexity:

    • O(1)O(1) for addScore.
    • O(1)O(1) for reset.
    • O(K)+O(NlogK)O(K) + O(N \text{log}K) = O(NlogK)O(N \text{log}K). It takes O(K)O(K) to construct the initial heap and then for the rest of the NKN-K elements, we perform the extractMin and add operations on the heap each of which take (logK)(\text{log}K) time.
  • Space Complexity:

    • O(N+K)O(N + K) where O(N)O(N) is used by the scores dictionary and O(K)O(K) is used by the heap.


Approach 3: Using a TreeMap / SortedMap

This approach is inspired by this discussion thread. Here we will try to improve on the overall time complexity of the top function at the expense of the time complexity of the addScore function. As discussed before, a heap doesn't have any properties that aid in search. At the end of the day, it is simply list of elements with certain properties associating them. However, these properties do not enhance the searchability of the data structure as a whole. We can definitely do enhancements where we maintain references to nodes in the heap, in a dictionary and then use those references for making updates. However, we will be looking at the TreeMap data structure (java) which uses the balanced-binary-search tree instead.

The great advantage we get with a balanced BST is that the search/add/remove operations are all bounded by a logarithmic complexity in terms of the number of elements in the tree. This is achievable due to the structure of the tree and the relationship between the subtrees and a root.

Algorithm

  1. Initialize a dictionary scores that will use the playerId as the key and score as the value.
  2. Initialize a TreeMap (java) or a SortedMap (python) called sortedScoreMap. The way this would be structured is that the key would be a score and the value would be the number of players that have this score. Imagine this being represented as a balanced BST with the keys being used for arranging the tree. We need the top function to use the scores and so, we use them as the key.
  3. addScore ~
    • Note the old score for the player. Let it be called oldScore.
    • Update the value of oldScore in sortedScoreMap TreeMap. If the value has reached 0, remove the score entry.
    • Simply update the dictionary with the new score for the player.
    • Add the updated value to the sortedScoreMap as well by incrementing the value by 1 i.e. one more player has this score.
    • If the player doesn't exist, initialize the score to score.
  4. top ~
    • Iterate over all the keys in the sortedScoreMap. Note that since the data structure is a BST, an inorder traversal of the keys would return them in the sorted order. We don't need to sort them again. Hence, we will simply iterate over the keys and pick the first K. Also, we have arranged the tree with each score mapped to how many players have that score. So there are no duplicates in the tree.
    • Pick the first K entries i.e. first K values.
      • For each key, multiply (key * value) and add it to the total sum.
      • Also, reduce the counter counting down to K by value.
  5. reset ~
    • Note the old score for the player. Let it be called oldScore.
    • Update the value of oldScore in sortedScoreMap TreeMap. If the value has reached 0, remove the score entry.
    • Delete the entry containing the playerId.

Implementation

Note that we are using SortedDict in Python. This is an external, apache licensed package that is supported by the Leetcode platform. You can read more about it here. We don't have a way to construct a reverse SortedDict in Python and hence, we negate the scores before adding them to the dict (TreeMap like data structure) so that the normal in-order traversal would give us the scores in the reverse order i.e. descending order.

Complexity Analysis

  • Time Complexity:

    • O(logN)O(\text{log}N) for addScore. This is because each addition to the BST takes a logarithmic time for search. The addition itself once the location of the parent is known, takes constant time.
    • O(logN)O(\text{log}N) for reset since we need to search for the score in the BST and then update/remove it. Note that this complexity is in the case when every player always maintains a unique score.
    • It takes O(K)O(K) for our top function since we simply iterate over the keys of the TreeMap and stop once we're done considering K scores. Note that if the data structure doesn't provide a natural iterator, then we can simply get a list of all the key-value pairs and they will naturally be sorted due to the nature of this data structure. In that case, the complexity would be O(N)O(N) since we would be forming a new list.
  • Space Complexity:

    • O(N)O(N) used by the scores dictionary. Also, if you obtain all the key-value pairs in a new list in the top function, then an additional O(N)O(N) would be used.


Report Article Issue

Comments: 6
sponomarev's avatar
Read More

In the Approach 3 there is no need to iterate over times, you can calculate how many players with score key you can take: can_take = min(K - count, times). And then sum += can_take * key.

2
Reply
Share
Report
hitzy's avatar
Read More

for Approach #3, please fix the summing part. Can sum up using count of remaining v/s needed:

class Leaderboard {

    Map<Integer, Integer> scores;
    TreeMap<Integer, Integer> sortedScores;
    
    public Leaderboard() {
        this.scores = new HashMap<Integer, Integer>();
        this.sortedScores = new TreeMap<>(Collections.reverseOrder());
    }
    
    public void addScore(int playerId, int score) {
        
        // The scores dictionary simply contains the mapping from the
        // playerId to their score. The sortedScores contain a BST with 
        // key as the score and value as the number of players that have
        // that score.        
        if (!this.scores.containsKey(playerId)) {
            this.scores.put(playerId, score);
            this.sortedScores.put(score, this.sortedScores.getOrDefault(score, 0) + 1);
        } else {
            
            // Since the current player's score is changing, we need to
            // update the sortedScores map to reduce count for the old
            // score.
            int preScore = this.scores.get(playerId);
            int playerCount = this.sortedScores.get(preScore);
            
            
            // If no player has this score, remov it from the tree.
            if (playerCount == 1) {
                this.sortedScores.remove(preScore);
            } else {
                this.sortedScores.put(preScore, playerCount - 1);
            }
            
            // Updated score
            int newScore = preScore + score;
            this.scores.put(playerId, newScore);
            this.sortedScores.put(newScore, this.sortedScores.getOrDefault(newScore, 0) + 1);
        }
    }
    
    public int top(int K) {
        int sum = 0;
        for (Map.Entry<Integer, Integer> e: this.sortedScores.entrySet()) {
            // Number of players that have this score.
            int times = Math.min(K, e.getValue());
            sum += times*e.getKey();
            K -= times;
            // Found top-K scores, break.
            if (K <= 0) {
                break;
            }
        }
        
        return sum;
    }
    
    public void reset(int playerId) {
        int preScore = this.scores.get(playerId);
        this.sortedScores.put(preScore, this.sortedScores.get(preScore) - 1);
        if (this.sortedScores.get(preScore) == 0) {
            this.sortedScores.remove(preScore);
        }
        
        this.scores.remove(playerId);
    }
}

0
Reply
Share
Report
flyingorange's avatar
Read More

I would love for the authors to also consider a solution based on Doubly LinkedList + HashMap!
My implementation beats 100% [Java], which was a surprise.
Heavily inspired by LRU Cache problem!
https://leetcode.com/problems/design-a-leaderboard/discuss/1214603/Java-beats-100-solution-Double-LinkedList-%2B-HashMap

0
Reply
Share
Report
laodasb's avatar
Read More

The time complexity to retrieve next operation is actually O(logn) in Java, here is the code from JDK:
/**
* Base class for TreeMap Iterators
*/
abstract class PrivateEntryIterator implements Iterator {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;

    PrivateEntryIterator(Entry<K,V> first) {
        expectedModCount = modCount;
        lastReturned = null;
        next = first;
    }

    public final boolean hasNext() {
        return next != null;
    }

    final Entry<K,V> nextEntry() {
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        next = successor(e);
        lastReturned = e;
        return e;
    }


/**
 * Returns the successor of the specified Entry, or null if no such.
 */
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.right != null) {
        Entry<K,V> p = t.right;
        while (p.left != null)
            p = p.left;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.right) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

/**
 * Returns the predecessor of the specified Entry, or null if no such.
 */
static <K,V> Entry<K,V> predecessor(Entry<K,V> t) {
    if (t == null)
        return null;
    else if (t.left != null) {
        Entry<K,V> p = t.left;
        while (p.right != null)
            p = p.right;
        return p;
    } else {
        Entry<K,V> p = t.parent;
        Entry<K,V> ch = t;
        while (p != null && ch == p.left) {
            ch = p;
            p = p.parent;
        }
        return p;
    }
}

Thus the topK method's time complexity is still actually O(KlogN) in Java, though maybe we can implement the above operations in amortized O(1) time by inorder traversal, but the space complexity would suffer.

0
Reply
Share
Report
go-away's avatar
Read More

The given solutions for Python are pretty trash. For example, the first solution uses defaultdict() but not defaultdict(int). Why? If you use defaultdict(int), then

def addScore(self, playerId: int, score: int) -> None:
        if playerId not in self.scores:
            self.scores[playerId] = 0
        self.scores[playerId] += score

can be simplified to

def addScore(self, playerId: int, score: int) -> None:
        self.scores[playerId] += score    

Then in the second solution you do

 res = 0
 while heap:
        res += heapq.heappop(heap)

This is so stupid, just do sum(heap). Calling heappop each time forces the heap to switch stuff around internally to maintain the heap invariant.

-1
Show 4 replies
Reply
Share
Report
vsingh58's avatar
Read More

I think the time complexity of top operation in Approach 3 is K logN. if every player has unique score then we pop the K times. each pop will result in rebalance of N-i items. where i from 1 to K

-4
Show 3 replies
Reply
Share
Report

You don't have any submissions yet.

1244/1883
Contribute
|||
Saved
#1201 Ugly Number III
Medium
#1202 Smallest String With Swaps
Medium
#1203 Sort Items by Groups Respecting Dependencies
Hard
#1204 Last Person to Fit in the Elevator
Medium
#1205 Monthly Transactions II
Medium
#1206 Design Skiplist
Hard
#1207 Unique Number of Occurrences
Easy
#1208 Get Equal Substrings Within Budget
Medium
#1209 Remove All Adjacent Duplicates in String II
Medium
#1210 Minimum Moves to Reach Target with Rotations
Hard
#1211 Queries Quality and Percentage
Easy
#1212 Team Scores in Football Tournament
Medium
#1213 Intersection of Three Sorted Arrays
Easy
#1214 Two Sum BSTs
Medium
#1215 Stepping Numbers
Medium
#1216 Valid Palindrome III
Hard
#1217 Minimum Cost to Move Chips to The Same Position
Easy
#1218 Longest Arithmetic Subsequence of Given Difference
Medium
#1219 Path with Maximum Gold
Medium
#1220 Count Vowels Permutation
Hard
#1221 Split a String in Balanced Strings
Easy
#1222 Queens That Can Attack the King
Medium
#1223 Dice Roll Simulation
Hard
#1224 Maximum Equal Frequency
Hard
#1225 Report Contiguous Dates
Hard
#1226 The Dining Philosophers
Medium
#1227 Airplane Seat Assignment Probability
Medium
#1228 Missing Number In Arithmetic Progression
Easy
#1229 Meeting Scheduler
Medium
#1230 Toss Strange Coins
Medium
#1231 Divide Chocolate
Hard
#1232 Check If It Is a Straight Line
Easy
#1233 Remove Sub-Folders from the Filesystem
Medium
#1234 Replace the Substring for Balanced String
Medium
#1235 Maximum Profit in Job Scheduling
Hard
#1236 Web Crawler
Medium
#1237 Find Positive Integer Solution for a Given Equation
Medium
#1238 Circular Permutation in Binary Representation
Medium
#1239 Maximum Length of a Concatenated String with Unique Characters
Medium
#1240 Tiling a Rectangle with the Fewest Squares
Hard
#1241 Number of Comments per Post
Easy
#1242 Web Crawler Multithreaded
Medium
#1243 Array Transformation
Easy
#1244 Design A Leaderboard
Medium
#1245 Tree Diameter
Medium
#1246 Palindrome Removal
Hard
#1247 Minimum Swaps to Make Strings Equal
Medium
#1248 Count Number of Nice Subarrays
Medium
#1249 Minimum Remove to Make Valid Parentheses
Medium
#1250 Check If It Is a Good Array
Hard